/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.*;

public class LexiconArrayList implements LexiconInterface
{
	ArrayList<String> values;

	/**
	 * Load the words from an input source and store them in this lexicon.
	 * 
	 * @param input
	 *            A scanner that will provide the entire dictionary.
	 */
	public void load(Scanner input)
	{
		values = new ArrayList<String>();
		String nextStr = input.next().toLowerCase();
		values.add(0, nextStr);

		while (input.hasNext())
		{
			nextStr = input.next().toLowerCase();
			addToLexicon(nextStr);
		}
	}

	/**
	 * Inserts str into the lexicon, using a binary search to find the correct position.
	 * 
	 * @param str the word to add to the lexicon
	 */
	private void addToLexicon(String str)
	{
		int high = values.size() - 1, mid = 0, low = 0;

		while (low <= high)
		{
			mid = (low + high) / 2;
			String string = values.get(mid);

			int temp = string.compareTo(str);

			if (temp == 0)
			{
				return; //duplicate word found
			}
			else if (temp < 0)
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		
		if (low != mid)
		{
			values.add(low, str);
		}
		else if (high != mid)
		{
			values.add(mid, str);
		}
	}

	/**
	 * If the prefix is in the lexicon, returns true.
	 * 
	 * @param s
	 *            The word to search for.
	 * @return True if the lexicon contains s.
	 */
	public boolean containsPrefix(String s)
	{
		int high = values.size() - 1, mid, low = 0;

		while (low <= high)
		{
			mid = (low + high) / 2;
			String string = values.get(mid);
			int temp = string.substring(0,
					Math.min(s.length(), string.length())).compareTo(s);

			if (temp == 0)
			{
				return true;
			}
			else if (temp < 0)
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		return false;
	}

	/**
	 * If the word is in the lexicon, returns true.
	 * 
	 * @param s
	 *            The word to search for.
	 * @return True if the lexicon contains s.
	 */
	public boolean contains(String s)
	{
		int high = values.size() - 1, mid, low = 0;
		while (low <= high)
		{
			mid = (low + high) / 2;
			int temp = s.compareTo(values.get(mid));
			
			if (temp == 0)
			{
				return true;
			}
			else if (temp > 0)
			{
				low = mid + 1;
			}
			else
			{
				high = mid - 1;
			}
		}
		return false;
	}

	/**
	 * returns an iterator over the lexicon of strings, used in LexiconFirstAutoPlayer 
	 */
	@Override
	public Iterator<String> iterator()
	{
		return values.iterator();
	}
}